C++ STL

Posted on | Edited on | In

输入输出

C++保留了C的scanf和printf，增加了额外的cin与cout

例子

C程序中输入输出

1
2
3
int a;
scanf("%d",&a);
printf("%d",a);

C++输入输出

1
2
3
int a;
cin>>a;
cout<<a;

连续输入输出变量

1
2
3
int a,b,c;
cin>>a>>b>>c;
cout<<a<<b<<c;

优雅地换行

1
2
3
4
cout<<1;
cout<<endl;
cout<<2;
cout<<3<<endl<<endl;

好处：

1.少写了很多东西

2.连续输入输出变量

3.换行优雅

注意：cin、cout比scanf、printf慢，有时候刷算法超时，可能因为使用了cin、cout 输入输出的数量(>1000)特别多，刷算法用cin，cout容易超时

STL(Standard Template Library)与algorithm头文件

STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。

algorithm是对容器继承的一些算法函数，辅助刷算法题

概念：迭代器——理解为指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int a[]={2,1,5,0,-1,5,9};
    sort(a,a+7);
    for(int i=0;i<7;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    system("pause");
    return 0;
}

string

概念：相当于char*的封装，理解为字符串

简单使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**C中定义字符串以及打印*/
char *ch="asdkajbf";
for(int i=0;ch[i]!='\0';i++) cout<<*(ch+i);
/**C++中*/
string s="ssadaffw";
cout<<s<<endl;
//字符转字符串
char c = 'a';
string s = string(1, c);

//初始化10个字符a为字符串
string tmp(10, 'a');

tolower(char c): 转成小写字母
toupper(char c): 如果c为小写英文字母，则返回对应的大写字母；否则返回原来的值。
isalnum(char c): 判断字符是字母或者数字
isdigit(char c):判断是否是数字

获取一行字符串

我想获取一行字符串

1
hello world

C中：

1
scanf("%s",ch);//1.仅获取一个单词，空格结束 2.ch[100]得设置初始大小

字符转字符串

  1. string构造方法

    char c = 'A';
 string s(1, c);

  2. push_back

    string s;
s.push_back(c);

  3. +=

    char c = 'A';
string s;
s += c;

C++中：

1
2
3
string s;
getline(cin,s);//获取一行数据
cout<<s;

字符串转数字atoi

std::string str = "123";
int n = atoi(str.c_str());
cout<<n; //123

+=运算符

+=对于字符串，字符有效，数字会转为asc码

1
2
3
4
5
6
7
8
string s;
s+="hello";
s+=" world";
s+='5';
s+=10;//10对应的asc码是换行
int a=5;//想把a加入字符串
s+=(a+'0');
cout<<s;

排序（使用algorithm）

1
2
3
string s="5418340";
sort(s.begin(),s.end());
cout<<s;

erase函数

1
2
3
4
5
/**begin是头迭代器，end是尾迭代器*/
string s="5418340";
s.erase(s.begin());//删除第一个
s.erase(--s.end());//删除最后一个
cout<<s;

substr子串函数

1
2
3
4
5
/**begin是头迭代器，end是尾迭代器*/
string s="5418340";
s=s.substr(1,3);//取418,取索引为1，往后截断3个
s=s.substr(1,-1);//索引为1，截断到最后
cout<<s;

reverse翻转函数

1
2
3
4
5
6
string str = "abcdefghijk";
cout<<"before reverse: "<<str<<endl;
reverse(str.begin(), str.end());
cout<<"after reverse: "<<str<<endl;
//before reverse: abcdefghijk
//after reverse: kjihgfedcba

在某些情况下，可能要手写reverse函数：

1
2
3
4
5
6
7
8
void reverse(string &str, string::iterator start, string::iterator end) {
    end--;
    while (start < end) {
        char tmp = *start;
        *start++ = *end;
        *end-- = tmp;
    }
}
1
2
3
4
5
6
7
8
9
void reverse(string &str) {
    unsigned long i = 0;
    unsigned long j = str.size()-1;
    while (i<j) {
        char tmp = str[i];
        str[i++] = str[j];
        str[j--] = tmp;
    }
}

sort函数

1
2
3
4
string str = "akjkkskkskbc0";
sort(str.begin(), str.end(), less<>());
cout<<"after sorted: "<<str<<endl;
// after sorted: 0abcjkkkkkkss

子串查找find

string的find()函数用于找出字母在字符串中的位置。

find(str,position)

find()的两个参数：可以不填第二个参数，默认从字符串的开头进行查找。

  • str：是要找的元素

  • position：字符串中的某个位置，表示从从这个位置开始的字符串中找指定元素。

  • 返回值为目标字符的位置，当没有找到目标字符时返回npos。
    string::npos其实就是-1

例1：找到目标字符的位置

1
2
3
string s = "hello world!";
cout << s.find("e") << endl;
结果为：1

例2：未找到目标字符

1
2
3
4
5
string s = "hello world!";
if (s.find("a") == s.npos) {
    cout << "404 not found" << endl;
}
结果为：404 not found

例3：指定查找位置

1
2
3
string s = "hello world!";
cout << s.find("l",5) << endl;
结果为：9

从空格开始（包含空格）的后半部分字符串中寻找字符”l”，结果找到了world中的”l”在整个字符串中的位置

例4：找到目标字符在字符串中第一次出现和最后一次出现的位置

1
2
3
4
5
6
7
string s = "hello world!";
cout << "first time occur in s:"<<s.find_first_of("l") << endl;
cout << "last time occur in s:" << s.find_last_of("l") << endl;
结果为：

first time occur in s:2
last time occur in s:9

例5：反向查找：

1
2
3
4
5
string s = "hello world!";
cout << s.rfind("l") << endl;
结果为：9

即从后往前第一次出现"l"的位置

to_string()

函数原型：

string to_string (int val);
string to_string (long val);
string to_string (long long v****al);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);

功能：

将数值转化为字符串。返回对应的字符串。

字符串遍历(4种)

  • for循环
1
2
string s="5418340";
for(int i=0;i<s.length();i++) cout<<s[i];
  • 迭代器
1
for(string::iterator it=s.begin();it!=s.end();it++) cout<<*it;
  • 迭代器化简
1
for(auto it=s.begin();it!=s.end();it++) cout<<*it;
  • 利用C++ 11新特性for循环
1
for(auto x:s) cout<<x;

vector

概念：vector相当于数组，模板类型相当于存放的内容

vector构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//定义一个空vector
vector<int> v;
//定义一个4个大小的vector，初始为0
vector<int> v2(4);
//定义一个4个大小的vector，初始为6
vector<int> v3(4,6);
// 直接用{1,2，3,4,5}数组字面量初始化
vector<int> v{1,2,3,4,5};

for(auto x:v3) cout<<x;

int a[] = {10, 21, -3};
//用数组及长度初始化方式一
vector<int> arr(a, a+3);
//用数组初始化方式二
std::vector<int> v = {7, 5, 16, 8};

用at或者[]获取元素

1
2
3
vector<int> v{1,2,3,4,5};
cout<<v[1];//取索引为1的
cout<<v.at(2);//取索引为2的

常用方法

  • push_back追加内容
1
2
3
4
5
6
7
vector<int> v;
v.push_back(5);
v.push_back(5);
v.push_back(5);
v.push_back(5);
v.push_back(6);
for(auto x:v) cout<<x;
  • resize进行重置大小
1
v.resize(10);//不赋值默认为0
  • erase删除元素，复杂度为O(n)
1
2
v.erase(v.begin());//删除第一个元素
v.erase(--v.end());//删除最后一个元素
  • 获取第一个元素，获取最后一个元素
1
2
3
4
5
6
7
8
/**获取第一个元素*/
cout<<v.front();
cout<<v[0];
cout<<*v.begin();
/**获取最后一个元素*/
cout<<v.back();
cout<<v[v.size()-1];//size是获取大小
cout<<*--v.end();
  • 插入元素
1
2
3
4
5
6
7
8
vector<int> vec;
vec.push_back(2);
vec.insert(vec.begin(), 1);
vec.insert(vec.end(), 1);
vec.insert(vec.end()-1, 1);
for(auto i : vec) {
    cout<<i<<endl;
}

排序

第三个参数为比较器，不写默认为less< int >(), 即从小到大排序

1
2
3
4
vector<int> v{5,1,2,5,4,0,-1};
sort(v.begin(),v.end(),less<int>());//从小到大
sort(v.begin(),v.end(),greater<int>());//从大到小排序
for(auto x:v) cout<<x;

遍历

1
2
3
4
5
6
7
8
9
10
11
12
//1.for循环遍历
vector<int> v{5,1,2,5,4,0,-1};
for(int i=0;i<v.size();i++) cout<<v[i];

//2.迭代器遍历
for(vector<int>::iterator it=v.begin();it!=v.end();it++) cout<<*it;

//3.迭代器简化循环
for(auto it=v.begin();it!=v.end();it++) cout<<*it;cout<<endl;
//4.c++11新特性****
for(auto x:v) cout<<x;
for(int x:v) cout<<x;

stack

概念：栈

构造

1
stack<int> s;

常用方法

  • push()、pop()、size()、empty()
  • push() 入栈一个元素
  • pop() 出栈一个元素，pop()无返回值
  • top() 取栈顶元素
  • size() 查看元素个数
  • empty()查询是否为空
1
2
3
4
5
6
7
s.push(2);
s.push(3);
cout<<s.top()<<endl;
s.pop();
cout<<s.top()<<endl;
cout<<s.size()<<endl;
cout<<s.empty()<<endl;

进制转换(十进制转二进制)

1
2
3
4
5
6
7
8
9
10
11
12
int itob(int decimal){
    stack<int> s;int res=0;
    while(decimal!=0){
        s.push(decimal%2);
        decimal/=2;
    }
    while(!s.empty()){
        res=res*10+s.top();
        s.pop();
    }
    return res;
}

逆序单词（拓展sstream，stoi，itoa）

输入一行字符串，将字符串逆序打印

输入：hello world my name is steve yu

输出：yu steve is name my world hello

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <stack>
#include <sstream>

using namespace std;

int main(){
    string str;
    stack<string> s;
    getline(cin,str);
    stringstream ss;
    ss<<str;
    while(ss>>str)
        s.push(str);
    while(!s.empty()){
        cout<<s.top();
        s.pop();
        if(s.size()!=0) cout<<" ";
    }
    return 0;
}

字符串转数字

  • 方法1:
1
2
3
4
5
6
string s="1234";
int i;
stringstream ss;
ss<<s;
ss>>i;
cout<<i;
  • 方法2:
1
2
3
string s="1234";
int i=stoi(s);
cout<<i;

数字转字符串

  • 方法1:
1
2
3
4
5
6
int a=1234;
string out;
stringstream ss;
ss<<a;
ss>>out;
cout<<out<<endl;
  • 方法2:(c++ 11)
1
2
int a=1234;
cout<<to_string(a)<<endl;

queue

队列是一种FIFO的线性数据结构。使用时要#include。

构造

1
queue<int> q;

常见方法

  • push()：从队尾进队列
  • pop()：从队头出队列
  • front()：获取队头元素
  • back()：获取队尾元素
  • size()：获取队列元素个数
1
2
3
4
5
6
7
q.push(5);
q.push(6);
cout<<q.front()<<endl;// 队头元素
q.pop();// 队头元素出队列
cout<<q.front()<<endl;
cout<<q.size()<<endl;
cout<<q.back()<<endl;// 队尾元素

priority_queue

概念：优先级队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。

在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

首先要包含头文件#include, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。

优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。优先队列可以以O(log n) 的效率查找一个队列中的最大值或者最小值，其中是最大值还是最小值是根据创建的优先队列的性质来决定的。

和队列基本操作相同:

  • top() 访问队头元素
  • empty() 队列是否为空
  • size() 返回队列内元素个数
  • push() 插入元素到队尾 (并排序)
  • emplace() 原地构造一个元素并插入队列
  • pop() 弹出队头元素
  • swap() 交换内容

优先级队列默认大顶堆，即元素从大到小排列。

初始化

priority_queue< Type, Container, Functional >

Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式。当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆，即降序队列。

//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆，默认
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

更为复杂的比较规则参考这里

  1. priority_queue默认初始化方式， 默认情况下，最大堆，元素从大到小排列

    srand(time(NULL));
priority_queue<int> q;
for(int i=0;i<10;i++){
    int num=rand()%10;
    q.push(num);
}

while(!q.empty()){
    count<<q.top()<<" ";
    q.pop();
}

  2. priority_queue, greater> q;

    这种初始化方式是最小堆，元素从小到大排列。

  3. 自定义比较方法

    bool myCmp(int a, int b){
    return a%10 < b%10;
}
priority_queue<int, vector<int>, function<bool(int, int)>> q(myCmp);

    这种初始化方式是按照个位数从大到小排列。

deque

双端队列是一种特殊的队列，用特殊的数据结构实现了在头尾都可进、出队列。

常见方法

  • push_back()：从队尾进队列
  • pop_back()：从队尾出队列
  • push_front()：从队头进队列
  • pop_front()：从队头出队列
  • front()：获取对头元素
  • back()：获取队尾元素
  • size()：获取队列元素个数
1
2
3
4
5
6
7
8
9
10
deque<int> d;
// 4 9 1 2
d.push_back(1);
d.push_back(2);
d.push_front(9);
d.push_front(4);
d.pop_back();
d.pop_front();
for(auto tmp:d) cout<<tmp<<endl;
for(auto it=d.begin();it!=d.end();it++) cout<<*it<<endl;

map

映射（map为树状表，unorderedmap为哈希表）。使用时要#include。

初始化

1
2
3
4
5
6
7
//自动初始化
map<int, string> hashMap;
//常量初始化
map<int, string> map = {{1, "1"}, {2, "2"}};

// 直接字面量初始化
map<char, char> dict = {{'(', ')'}, {'{', '}'}, {'[', ']'}};

常见方法

  • 插入
1
2
3
4
5
6
7
8
// insert pair
hashMap.insert(pair<int, string>(1, "1111"));
hashMap.insert(pair<int, string>(2, "2222"));
// insert make_pair
hashMap.insert(make_pair(5, "66060"));
// insert by key
hashMap[8] = "8888";
hashMap[3] = "3333";
  • 查找

find():使用find，返回的是被查找元素的位置，没有则返回map.end()

1
2
3
if (hashMap.find(11)!=hashMap.end()) {
    hashMap.erase(hashMap.find(11));
}

count(key):使用count，返回的是被查找元素的个数。如果有，返回1；否则，返回0。注意，map中不存在相同元素，所以返回值只能是1或0。

1
2
3
if (hashMap.count(11)!=0) {
    //存在key
}
  • 删除
1
2
3
4
// delete by iterator
hashMap.erase(hashMap.begin());
// delete by key
hashMap.erase(3);
  • 遍历/倒序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
map<int,int> m;//有序的，树状结构（底层）
m[6]=3;
m[5]=8;
m[4]=9;
for(auto it=m.begin();it!=m.end();it++)
	cout<<it->first<<" "<<it->second<<endl;
for(auto tmp:m){
	cout<<tmp.first<<" "<<tmp.second<<endl;
}

map<int, string>:: reverse_iterator rp;
for (rp = hashMap.rbegin(); rp != hashMap.rend(); rp++) {
    cout << " map [ " << rp->first << "  :  " << rp->second<< " ]"<< endl;
}

map转成vector进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first>b.first;
}
int main(){
    unordered_map<int,int> m;//无序的，哈希结构（底层）
    m[6]=3;
    m[5]=8;
    m[4]=9;
    vector<pair<int,int>> v(m.begin(),m.end());
    sort(v.begin(),v.end(),cmp);
    for(auto tmp:v){
        cout<<tmp.first<<tmp.second<<endl;
    }
    return 0;
}

unordered_map

unordered_map是哈希结构实现的map， 查找、插入的时间复杂度都是O(1)

1
2
3
4
5
6
7
8
9
unordered_map<int,int> m;
m[6]=3;
m[5]=8;
m[4]=9;
for(auto it=m.begin();it!=m.end();it++)
	cout<<it->first<<" "<<it->second<<endl;
for(auto tmp:m){
	cout<<tmp.first<<" "<<tmp.second<<endl;
}

set

基于树状结构实现，集合内元素有序且不包含重复元素。

常用方法

  • insert()
  • sort()
  • size()
  • empty()
1
2
3
4
5
6
7
8
9
10
11
12
set<int> s;
s.insert(3);
s.insert(4);
s.insert(4);
s.insert(4);
cout<<s.size()<<endl;
for(auto tmp:s)
	cout<<tmp<<" ";
cout<<endl;
for(auto it=s.begin();it!=s.end();it++)
	cout<<*it<<" ";
cout<<endl;
  • 查找find() 和 count()
1
2
set.find(item)!=set.end() //item存在于set中
set.count(item)>0 //item存在于set,由于去重过，所以只会是0、1
  • 删除erase()
1
2
3
4
5
set<int>::iterator p = set.find(item);
if(p != set.end()){
	cout<<"删除元素"<<*p<<" ";
	set.erase(p);
}

unordered_set

基于哈希结构实现，集合内元素无序，查找O(1)

list

双向链表

1
2
3
4
5
6
7
8
list<int> li;
li.push_back(6);
li.push_front(5);
li.emplace_front(9);
li.emplace_back(10);
li.insert(++li.begin(),2);
for(auto tmp:li) cout<<tmp<<endl;
for(auto it=li.begin();it!=li.end();it++) cout<<*it<<endl;

文档

英文：

http://www.cplusplus.com/reference/stl/

中文：

http://c.biancheng.net/stl/map/